import java.util.*;
/**
 * 347. Top K Frequent Elements 前K个高频元素
 * https://leetcode.com/problems/top-k-frequent-elements/
 */
class TopKFrequentElements {
    /**
     * 方法：使用最小堆维护前k个最频繁元素
     * 
     * Args:
     *   nums: int[], 输入数组
     *   k: int, 需要返回的最频繁元素的数量
     * 
     * Returns:
     *   int[]: 前k个最频繁元素的数组
     * 
     * Time: O(nlogk), 其中n是数组长度，每次堆操作需要O(logk)时间
     * Space: O(n), 需要存储所有元素的频率
     */
    public int[] topKFrequent(int[] nums, int k) {
        // 第一步：统计每个元素的出现次数
        Map<Integer, Integer> count = new HashMap<>();
        for(int x : nums){
            count.merge(x, 1, Integer::sum);
        }
        // 使用最小堆
        PriorityQueue<Map.Entry<Integer, Integer>> heap = 
            new PriorityQueue<>((a, b) -> a.getValue() - b.getValue());
        for(Map.Entry<Integer, Integer> entry : count.entrySet()){
            if(heap.size() < k){
                heap.offer(entry);
            } else if(entry.getValue() > heap.peek().getValue()){
                heap.poll();
                heap.offer(entry);
            }
        }
        int[] res = new int[k];
        for(int i = 0; i< k; i++){
            res[i] = heap.poll().getKey();
        }
        return res;
    }

    /**
     * 方法：桶排序法
     * 使用桶排序的思想，将相同频率的元素放入同一个桶中，然后从高频率桶开始收集元素，直到收集到k个元素为止。
     * 
     * Args:
     *   nums: int[], 输入数组
     *   k: int, 需要返回的最频繁元素的数量
     * 
     * Returns:
     *   int[]: 前k个最频繁元素的数组
     * 
     * Time: O(n), 其中n是数组长度，统计频率O(n)，构建桶O(n)，收集结果O(k)
     * Space: O(n), 需要存储所有元素的频率和桶
     */
    public int[] topKFrequent1(int[] nums, int k) {
        // 第一步：统计每个元素的出现次数
        Map<Integer, Integer> cnt = new HashMap<>();
        for(int x : nums){
            cnt.merge(x, 1, Integer::sum);
        }
        int maxCnt = Collections.max(cnt.values());
        // 第二步：把出现次数相同的元素，放到同一个桶中
        List<Integer>[] buckets = new ArrayList[maxCnt + 1];
        Arrays.setAll(buckets, i -> new ArrayList<>());
        for(Map.Entry<Integer, Integer> e : cnt.entrySet()){
            buckets[e.getValue()].add(e.getKey());
        }
        // 第三步：倒序遍历 buckets，把出现次数前 k 大的元素加入答案
        int[] ans = new int[k];
        int j = 0;
        for(int i = maxCnt; i >= 0 && j < k; i--){
            for(int x : buckets[i]){
                ans[j++] = x;
            }
        }
        return ans;
    }
}